package 动态规划.背包And分组And切割问题系列;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Set;

/**
 * @author aodre , QQ : 480029069
 * @date 2023/3/22 16:28
 */
public class leetcode2597美丽子集的数目 {
    /*
     这个 先用递归写一下,
     再去思考一下 arignote 的 思想!

     == 注意一手 评论区的思路!
     */


    // 先写 一个 递归版本的  error; 还是重新 引入 自己的思考为好!

    public int recursion(int index, int k, Set<Integer> set, int[] nums) {
        if (index == nums.length) {
            return 1;
        }
        int ans = 0;
        // no choose
        ans = recursion(index + 1, k, set, nums);
        // choose , 看看能不能选择
        if (!set.contains(nums[index] - k) && !set.contains(nums[index] + k)) {
            set.add(nums[index]);
            ans += recursion(index + 1, k, set, nums);
            set.remove(nums[index]);
        }
//        Long
        return ans;
    }

    /*
     其实 arignote ， 这就是 暴力递归！
     考虑 重复值的 一个 情况，所以 不能用 set， 上面就是因为重复值的一个情况！
     */
    class Solution {

        public int beautifulSubsets(int[] nums, int k) {
            /*
             排个序， 是为了， 判断index 的时候， 只用考虑 nums[index] - k
             */
            Arrays.sort(nums);
            return beautifulSubsets(0, new HashMap<>(), nums, k) - 1;
        }

        private int beautifulSubsets(int index, HashMap<Integer, Integer> map, int[] nums, int k) {
            if (index == nums.length) {
                return 1;
            }
            int count = beautifulSubsets(index + 1, map, nums, k);
            if (map.getOrDefault(nums[index] - k, 0) == 0) {
                map.put(nums[index], map.getOrDefault(nums[index], 0) + 1);
                count += beautifulSubsets(index + 1, map, nums, k);
                map.put(nums[index], map.get(nums[index]) - 1);
            }
            return count;
        }
    }


    public static void main(String[] args) {
        System.out.println(Long.MAX_VALUE);
        System.out.println(Double.MIN_VALUE);
    }

}
